package leetcode_1000;

import java.util.Set;
import java.util.TreeSet;

/**
 *@author 周杨
 *LargestTimeForGivenDigits_949 给定4个数字 问能排列成的最大时间
 *describe:dfs求最大串
 *2018年12月2日 下午6:39:37
 */
public class LargestTimeForGivenDigits_949 {
	public static void main(String[] args) {
		LargestTimeForGivenDigits_949 test=new LargestTimeForGivenDigits_949();
		test.largestTimeFromDigits(new int[] {1,2,3,4});
	}
	
	public String largestTimeFromDigits(int[] A) {
       TreeSet<String> set=new TreeSet<String>();
       boolean visited[]=new boolean[4];
       dfs(A,visited,set,new StringBuilder());
       if(set.size()==0)
    	   return "";
       StringBuilder sb=new StringBuilder(set.last());
       sb.insert(2, ":");
       return sb.toString();
    }
	
	public void dfs(int[] A,boolean[] visited,Set<String>set,StringBuilder sb) {
		for(int i=0;i<4;++i) {
			if(!visited[i]) {
				sb.append(A[i]);
				if(sb.length()==4) {
					if(help(sb.toString()))
						set.add(sb.toString());
					sb.deleteCharAt(sb.length()-1);
					return ;
				}
				visited[i]=true;
				dfs(A,visited,set,sb);
				sb.deleteCharAt(sb.length()-1);
				visited[i]=false;	
			}
		}
	}
	
	public  boolean help(String s) {
		if(s.substring(0, 2).compareTo("23")>=1)
			return false;
		if(s.substring(2,4).compareTo("59")>=1)
			return false;
		return true;
	}
}
